package OJPractice;

import MAIN.ListNode;

import java.util.*;

public class newCoderPractice {
    public static void main(String[] args) {
        // 测试全排列
        int[] arr = {1,2,3};
        //List<List<Integer>> ret = permute(arr);
//        char c = '帅';
//        System.out.println(c);
    }

    // 递归+回溯模块刷题 （宏观看待递归问题）
    // 汉诺塔问题
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        dfs(A, B, C, A.size());
    }
    public void dfs(List<Integer> A, List<Integer> B, List<Integer> C, int size) {
        if (size == 1) {
            C.add(A.remove(A.size() - 1));
            return;
        }
        dfs(A, C, B, size - 1);
        C.add(A.remove(A.size() - 1));
        dfs(B, A, C, size-1);
    }

    // 合并两个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        if (list1.value < list2.value) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list2.next, list1);
            return list2;
        }
    }

    // 反转链表
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return head;
    }

    // 两两交换链表中的节点
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode tmp = swapPairs(head.next.next);
        ListNode newHead = head.next;
        newHead.next = head;
        head.next = tmp;
        return newHead;
    }

    // Pow(x, n)
    public double myPow(double x, int n) {
        return n < 0 ? 1.0 / pow(x, -n) : pow(x, n);
    }
    public double pow(double x, int n) {
        if (n == 0) return 1;
        double tmp = pow(x, n/2);
        return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
    }

    // 二叉树的深搜
    // 计算布尔二叉树的值
//    public boolean evaluateTree(TreeNode root) {
//        // 因为是完整二叉树，就判断一个就行了
//        if (root.left == null) return root.val == 0 ? false : true;
//        boolean leftTree = evaluateTree(root.left);
//        boolean rightTree = evaluateTree(root.right);
//        if (root.val == 2) return leftTree | rightTree;
//        else return leftTree & rightTree;
//    }

    // 求根节点到叶节点数字之和
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }
    public int dfs (TreeNode root, int preSum) {
        preSum = preSum * 10 + root.val;
        if (root.left == null && root.right == null) return preSum;
        int ret = 0;
        if (root.left != null) ret += dfs(root.left, preSum);
        if (root.right != null) ret += dfs(root.right, preSum);
        return ret;
    }

    // 二叉树剪枝
    public TreeNode pruneTree(TreeNode root) {
        if (root == null) return null;
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if (root.left == null && root.right == null && root.val == 0)
            root = null;
        return root;
    }

    // 验证二叉搜索树
    public long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        // 中序遍历处理看整体遍历之后的序列是否是有序的
        if (root == null) return true;
        boolean leftTree = isValidBST(root.left);
        boolean cur = false;
        if (root.val > prev) cur = true;
        if (cur == false) return false;
        prev = root.val;
        boolean rightTree = isValidBST(root.right);
        return leftTree && rightTree;
    }

    // 二叉搜索树中第k小的元素
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        dfs(root);
        return ret;
    }
    public int count;
    public int ret = 0;
    public void dfs(TreeNode root) {
        if (root == null || count == 0) return;
        dfs(root.left);
        count--;
        if (count == 0) {
            ret = root.val;
            return;
        }
        dfs(root.right);
    }

    // 二叉树的所有路径
    List<String> ret1 = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        dfs(root, new StringBuilder());
        return ret1;
    }
    public void dfs(TreeNode root, StringBuilder _path) {
        if (root == null) return;
        StringBuilder path = new StringBuilder(_path);
        // 前序遍历处理所有路径
        path.append(root.val);
        if (root.left == null && root.right == null) {
            ret1.add(path.toString());
            return;
        }
        path.append("->");
        if(root.left != null) dfs(root.left, path);
        if(root.right != null) dfs(root.right, path);
    }

    // 全排列
    public static List<List<Integer>> res;
    public static List<Integer> path;
    public static boolean[] check;
    public static List<List<Integer>> permute(int[] nums) {
        int len = nums.length;
        res = new ArrayList<>();
        path = new ArrayList<>();
        check = new boolean[len];
        dfs(nums);
        return res;
    }
    public static void dfs(int[] nums) {
        // 递归出口
        if (nums.length == path.size()) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (check[i] == false) {
                path.add(nums[i]);
                check[i] = true;
                dfs(nums);
                check[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }

    // 子集
    /*List<List<Integer>> ret;
    List<Integer> path;
    public List<List<Integer>> subsets(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        dfs(nums, 0);
        return ret;
    }
    public void dfs(int[] nums, int pos) {
        if (pos == nums.length) {
            ret.add(new ArrayList<>(path));
            return;
        }
        // 选
        path.add(nums[pos]);
        dfs(nums, pos + 1);
        path.remove(path.size() - 1);
        // 不选
        dfs(nums, pos + 1);
    }*/

    // 找出所有子集的异或总和再求和
    int sum;
    int path2;
    public int subsetXORSum(int[] nums) {
        dfs(nums, 0);
        return sum;
    }
    public void dfs(int[] nums, int pos) {
        sum += path2;
        for (int i = pos; i < nums.length; i++) {
            path2 ^= nums[i];
            dfs(nums, i + 1);
            path2 ^= nums[i];
        }
    }

    // 全排列 II
//    List<List<Integer>> ret;
//    List<Integer> path;
//    boolean[] check;
//    public List<List<Integer>> permuteUnique(int[] nums) {
//        ret = new ArrayList<>();
//        path = new ArrayList<>();
//        check = new boolean[nums.length];
//        Arrays.sort(nums);
//        dfs(nums, 0);
//        return ret;
//    }
//    public void dfs(int[] nums, int pos) {
//        // 递归出口
//        if (pos == nums.length) {
//            ret.add(new ArrayList<>(path));
//            return;
//        }
//        for (int i = 0; i < nums.length; i++) {
//
//            if (check[i] == false && (i == 0 || nums[i] != nums[i-1] || check[i - 1] == true)) {
//                path.add(nums[i]);
//                check[i] = true;
//                dfs(nums, pos + 1);
//                path.remove(path.size() - 1);
//                check[i] = false;
//            }
//        }
//    }

    // 电话号码组合
//    String[] tmp = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
//    StringBuilder path;
//    List<String> ret;
//    public List<String> letterCombinations(String digits) {
//        path = new StringBuilder();
//        ret = new ArrayList<>();
//        if (digits.length() == 0) return ret;
//        dfs(digits, 0);
//        return ret;
//    }
//    public void dfs(String digits, int pos) {
//        // 找到数字之间的映射关系
//        //String[] strs = digits.split("");
//        // 递归出口
//        if (pos == digits.length()) {
//            ret.add(path.toString());
//            return;
//        }
//        String cur = tmp[digits.charAt(pos) - '0'];
//        for(int i = 0; i < cur.length(); i++) {
//            path.append(cur.charAt(i));
//            dfs(digits, pos + 1);
//            path.deleteCharAt(path.length() - 1);
//        }
//    }

    //括号生成
//    int left, right, n;
//    StringBuilder path;
//    List<String> ret;
//    public List<String> generateParenthesis(int _n) {
//        n = _n;
//        path = new StringBuilder();
//        ret = new ArrayList<>();
//        dfs();
//        return ret;
//    }
//    public void dfs() {
//        if (right == n) {
//            ret.add(path.toString());
//            return;
//        }
//        if (left < n) {
//            path.append('(');
//            left++;
//            dfs();
//            path.deleteCharAt(path.length() - 1);
//            left--;
//        }
//        if (right < left) {
//            path.append(')');
//            right++;
//            dfs();
//            path.deleteCharAt(path.length() - 1);
//            right--;
//        }
//    }

    // 组合
    /*List<Integer> path;
    List<List<Integer>> ret;
    int n, k;
    public List<List<Integer>> combine(int _n, int _k) {
        path = new ArrayList<>();
        ret = new ArrayList<>();
        n = _n;
        k = _k;
        dfs(1);
        return ret;
    }
    public void dfs(int pos) {
        // 递归出口
        if (k == path.size()) {
            ret.add(new ArrayList<>(path));
            return;
        }
        // 函数体
        // 剪枝就不用做了，此时从i + 1 位置开始添加元素就是剪枝的操作
        for (int i = pos; i <= n; i++) {
            path.add(i);
            dfs(i + 1);
            // 恢复现场
            path.remove(path.size() - 1);
        }
    }*/







    // 合并两个有序数组
    public static void merge(int[] array1, int m, int[] array2, int n) {
        int p1 = 0, p2 = 0;
        int[] res = new int[m + n];
        int cur;
        while (p1 < m || p2 < n) {
            if (p1 == m) cur = array2[p2++];
            else if (p2 == n) cur = array1[p1++];
            else if (array1[p1] < array2[p2]) cur = array1[p1++];
            else cur = array2[p2++];
            res[p1 + p2 - 1] = cur;
        }
        for (int i = 0; i < m + n; i++) {
            array1[i] = res[i];
        }
    }

    // 目标和
    /*int ret, aim;
    public int findTargetSumWays(int[] nums, int target) {
        aim = target;
        dfs(nums, 0, 0);
        return ret;
    }
    public void dfs(int[] nums, int pos, int path) {
        //递归出口
        if (pos == nums.length) {
            if (path == aim) ret++;
            return;
        }
        // 加法
        dfs(nums, pos + 1, path + nums[pos]);
        // 减法
        dfs(nums, pos + 1, path - nums[pos]);
    }*/

    // 组合总和
    /*int aim;
    List<Integer> path;
    List<List<Integer>> ret;
    public List<List<Integer>> combinationSum(int[] nums, int target) {
        aim = target;
        path = new ArrayList<>();
        ret = new ArrayList<>();
        dfs(nums, 0, 0);
        return ret;
    }
    public void dfs(int[] nums, int pos, int sum) {
        if (aim == sum) {
            ret.add(new ArrayList<>(path));
            return;
        }
        if (sum > aim) return;  // 剪枝操作

        for (int i = pos; i < nums.length; i++) {
            path.add(nums[i]);
            dfs(nums, i, sum + nums[i]);// 此时还是从i位置开始进行选择，
            // 而不是在开始开头的所有的位置选择，这就是一步剪枝操作
            path.remove(path.size() - 1); // 恢复现场操作
        }
    }*/



    // 相交链表
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode cur1 = headA;
        ListNode cur2 = headB;
        int len1 = 0, len2 = 0;
        while (cur1 != null) {
            len1++;
            cur1 = cur1.next;
        }
        while (cur2 != null) {
            len2++;
            cur2 = cur2.next;
        }
        cur1 = headA;
        cur2 = headB;
        int len = len1 - len2;
        while (len != 0) {
            if (len > 0) {
                cur1 = cur1.next;
                len1--;
            } else {
                cur2 = cur2.next;
                len2--;
            }
        }
        while (cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }

    // 最小栈
    Stack<Integer> stack = null;
    Stack<Integer> minStack = null;
//    public MinStack() {
//        stack = new Stack<>();
//        minStack = new Stack<>();
//    }
    public void push(int val) {
        stack.push(val);
        if (minStack.empty()) {
            minStack.push(val);
        }else {
            //细节：此时一定要取=，也就是说如果minStack中的最小值和val相等
            //此时如果不放，出元素出一个最小值，最小栈也出一个最小值，之后这个
            //最小值就没有了
            if (val <= minStack.peek()) {
                minStack.push(val);
            }
        }
    }
    public void pop() {
        if (!stack.isEmpty()) {
            Integer val = stack.pop();
            //如果出的元素和最小栈中的相等，
            //此时最小栈也要出这个元素
            if (val.equals(minStack.peek())) {
                minStack.pop();
            }
        }
    }
    public int top() {
        if (!stack.isEmpty()) {
            return stack.peek();
        }
        return -1;
    }
    public int getMin() {
        return minStack.peek();
    }

    // 买卖股票的最佳时机
    public int maxProfit(int[] nums) {
        int l = 0;
        int r = 1;
        int res = 0;
        for (int i = 0; i < nums.length && r < nums.length; i++) {
            if (nums[l] >= nums[r]) {
                l = r;
            } else {
                if (res < nums[r] - nums[l]) {
                    res = nums[r] - nums[l];
                }
            }
            r++;
        }
        return res;
    }

    // 字符串转整数
    public int myAtoi(String s) {
        int len = s.length();
        char[] chars = s.toCharArray();
        // 去掉前导空格
        int index = 0;
        while (index < len && chars[index] == ' ') index++;
        if (index == len) return 0;
        // 如果出现符号字符，只有第一个有效
        int flg = 1;
        char firstChar = chars[index];
        if (firstChar == '+'){
            index++;
        } else if (firstChar == '-') {
            index++;
            flg = -1;
        }
        // 转换后续字符串
        int res = 0;
        while (index < len) {
            char curCh = chars[index];
            if (curCh > '9' || curCh < '0') break;
            if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 &&
                    (curCh - '0') > Integer.MAX_VALUE % 10)) {
                return Integer.MAX_VALUE;
            }
            if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 &&
                    (curCh - '0') > -(Integer.MIN_VALUE % 10))) {
                return Integer.MIN_VALUE;
            }

            res = res * 10 + flg * (curCh - '0');
            index++;
        }
        return res;
    }

    // 整数反转
    public static int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            if (rev < Integer.MIN_VALUE / 10 || rev > Integer.MAX_VALUE / 10) return 0;
            int digit = x % 10;
            x /= 10;
            rev = rev * 10 + digit;
        }
        return rev;
    }
}
